package com.LeetCode.MapAndList;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

/**
 * 最近最少使用缓存
 */
public class LFUCache {

    private class CacheNode{
        int key;
        int value;
        int freq = 1;

        public CacheNode(int k, int v){
            this.key = k;
            this.value = v;
        }
    }

    private Map<Integer,CacheNode> cache;

    private Map<Integer, LinkedHashSet<CacheNode>> freqMap;//可以通过使用次数查到对应的节点缓存列表

    private int capacity;
    private int size;
    private int min; //当前最小频次的组

    public LFUCache(int capacity){
        cache = new HashMap<>();
        freqMap = new HashMap<>();
        this.capacity = capacity;
    }

    public void put(int key, int value){
        if(capacity == 0) {
            return;
        }
        CacheNode node = cache.get(key);
        if(node != null){
            node.value = value;
            //在使用列表中计数
            freqInc(node);
        }else{
            if(size == capacity){
                CacheNode deadNode = removeCacheNode();
                cache.remove(deadNode);
                size--;
            }
            CacheNode newNode = new CacheNode(key,value);
            cache.put(key,newNode);
            addCacheNode(newNode);
            size++;
        }
    }

    public int get(int key){
        CacheNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        freqInc(node);
        return node.value;
    }


    private void freqInc(CacheNode node){
        int freq = node.freq;
        LinkedHashSet<CacheNode> set = freqMap.get(freq);
        set.remove(node);
        if(freq == min && set.size() == 0){//更新全局最小使用次数
            min = freq + 1;
        }
        //添加使用次数
        node.freq++;
        LinkedHashSet<CacheNode> newSet = freqMap.get(freq+1);
        if(newSet == null){
            newSet = new LinkedHashSet<>();
            freqMap.put(freq + 1, newSet);
        }
        newSet.add(node);
    }

    public void addCacheNode(CacheNode node){
        LinkedHashSet<CacheNode> set = freqMap.get(1);
        if(set == null){
            set = new LinkedHashSet<>();
            freqMap.put(1, set);
        }
        set.add(node);
        min = 1;
    }

    public CacheNode removeCacheNode(){
        LinkedHashSet<CacheNode> set = freqMap.get(min);
        CacheNode deadNode = set.iterator().next();
        set.remove(deadNode);
        return deadNode;
    }

}
































